/*
 *  sort array and return the number of inversions
 */
package algs4.sort;

public class Inversions
{
    /* Static Methods */
    public static int insertion(Comparable[] a) {
        int count = 0;
        int n     = a.length;

        for (int i = 1; i < n; i++) {
            int j        = i;
            Comparable v = a[i];

            for (; j > 0 && v.compareTo(a[j-1]) < 0; j--)
                a[j] = a[j-1];

            a[j] = v;

            count += i - j;
        }

        return count;
    }

    // merge sort
    public static int sort(Comparable[] a) {
        Comparable[] aux = a.clone();

        return sort(a, aux, 0, a.length - 1);
    }

    // sort dst by src from st to ed
    private static int sort(Comparable[] dst, Comparable[] src, int st, int ed) {
        // base case
        if (ed <= st) return 0;

        int count = 0;
        int mid   = (st + ed) / 2;

        count += sort(src, dst, st, mid);
        count += sort(src, dst, mid + 1, ed);

        count += merge(dst, src, st, mid, ed);

        return count;
    }

    // merge src to dst
    private static int merge(Comparable[] dst, Comparable[] src, int st, int mid, int ed) {
        int i = st;
        int j = mid + 1;
        int k = st;

        int count = 0;

        while (i <= mid && j <= ed) {
            if (src[i].compareTo(src[j]) > 0) { dst[k++] = src[j++]; count += mid - i + 1; }
            else                              { dst[k++] = src[i++];                       }
        }

        while (i <= mid) dst[k++] = src[i++];
        while (j <= ed)  dst[k++] = src[j++];

        return count;
    }

    /* Main Test */
    public static void main(String[] args) {
        Integer[] a = {0, 1, 5, 3, 3, 5, 2, 4};

        System.out.println("inversions: " + insertion(a));
        System.out.println("inversions: " + sort(a));
    }
}
